
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<Windows.h>
typedef struct LNode* PtrToLNode;
typedef int ElementType;
struct LNode {
	ElementType Data1, Data2;
	//Data1用来存系数，Data2用来存指数
	PtrToLNode Next;
};
typedef PtrToLNode List;
List makeEmpty() {//创建一个空链表并且将第一个节点空置
	List L = (List)malloc(sizeof(struct LNode));
	L->Next = NULL;
	return L;
}
int Length(List L) {//计算链表的长度
	//因为第一个节点是没有数据的，所以要从第二个节点开始计数
	List p = L->Next;
	int cut = 0;
	while (p != NULL) {
		cut++;
		p = p->Next;
	}
	return cut;
}
void Findkth(List L, int k) {//在链表中查找第k个元素
	List p = L->Next;
	int cnt = 1;
	while (p != NULL && cnt < k) {
		p = p->Next;
		cnt++;
	}
	if (cnt == k) {
		printf("第%d个元素为：", k);
		if (p->Data2 == 0)printf("%d\n", p->Data1);
		else printf("%dX^%d\n", p->Data1, p->Data2);
	}
	else 
		printf("在链表中没有第%d个元素\n", k);
}
List Find(List L, ElementType x) {//在链表中查找元素x的位置
	//因为在多项式中，指数才是唯一的，所以x应该是为指数
	List p = L->Next;
	while (p && p->Data2 != x) p = p->Next;
	if (p)return p;
	else return NULL;
}
List Insert(List L, ElementType x, ElementType y, int i) {//插入函数
	List tmp = (List)malloc(sizeof(struct LNode));
	tmp->Data1 = x; tmp->Data2 = y;
	int cnt = 0;
	List p = L;
	while (p && cnt < i - 1) {
		p = p->Next;
		cnt++;
	}
	if (p == NULL || cnt != i - 1) 
		printf("插入位置的参数错误\n!");
	else {
		tmp->Next = p->Next;
		p->Next = tmp;
	}
	return L;
}
List Delete(List L, int i) {//将第i个元素删除
	List tmp, p = L;
	int cnt = 0;
	while (p && cnt < i - 1) {
		p = p->Next;
		cnt++;
	}
	if (p == NULL || cnt != i - 1 || p->Next == NULL)printf("删除位置参数错误！\n");
	else {
		tmp = p->Next;
		p->Next = tmp->Next;
		free(tmp);
	}
	return L;
}
void print(List L) {//打印相加之后的多项式
	if (L->Next == NULL) {//如果链表中没有数据，直接退出函数
		printf("0\n");
		return;
	}
	List p = L->Next;
	if (p->Data1 != 0) printf("%d*X^%d", p->Data1, p->Data2);
	else printf("0");
	p = L->Next->Next;
	while (p != NULL) {
		if (p->Data1 == 0) {
			p = p->Next;
			continue;
		}
		if (p->Data1 == 1) {
			if (p->Data2 == 0) {
				if (p->Data1 < 0) printf("%d", p->Data1);
				else printf("+%d", p->Data1);
			}
			else if (p->Data2 == 1) {
				if (p->Data1 < 0)printf("X");
				else printf("+X", p->Data1);
			}
			else {
				if (p->Data1 < 0)printf("X^%d", p->Data1, p->Data2);
				else printf("+X^%d", p->Data1, p->Data2);
			}
		}
		else {
			if (p->Data2 == 0) {
				if (p->Data1 < 0) printf("%d", p->Data1);
				else printf("+%d", p->Data1);
			}
			else if(p->Data2==1){
				if (p->Data1 < 0)printf("%d*X", p->Data1);
				else printf("+%d*X", p->Data1);
			}
			else {
				if (p->Data1 < 0)printf("%d*X^%d", p->Data1, p->Data2);
				else printf("+%d*X^%d", p->Data1, p->Data2);
			}
		}
		p = p->Next;
	}
	printf("\n");
}
List List_sort(List L) {
	if (L->Next == NULL)return L;//如何链表中没有有效的元素，直接返回L
	List p, q;
	p = L->Next;
	int i = 0;
	for (p = L->Next; p!= NULL; p = p->Next) //见链表中的元素按指数大小进行排序
		for (q = p->Next; q!= NULL; q = q->Next) //选择排序
			if (p->Data2 < q->Data2) {
				ElementType t = p->Data2;
				p->Data2 = q->Data2;
				q->Data2 = t;
				t = p->Data1;
				p->Data1 = q->Data1;
				q->Data1 = t;
			}
	return L;
}
List add(List a, List b) {
	List p = b->Next;
	while (p != NULL) {
		List q = a->Next;
		int flag = 0;
		while (q != NULL) {
			if (p->Data2 == q->Data2) {//如果两个链表的指数相等，就将两个链表中的对应系数相加
				q->Data1 += p->Data1;
				flag = 1;
			}
			q = q->Next;
		}
		if (flag == 0)Insert(a, p->Data1, p->Data2, Length(a) + 1);
		p = p->Next;
	}
	return a;
}
#include<stdio.h> 
List Multiplication(List a, List b) {//将两个多项式相乘的函数
	List c = makeEmpty();//重新创建一个链表来存相乘之后的数据
	List p = a->Next;
	List d = c;
	while (p != NULL) {//两层循环把连个链表遍历
		List q = b->Next;
		while (q != NULL) {
			List s = (List)malloc(sizeof(struct LNode));
			s->Data1 = p->Data1 * q->Data1;
			s->Data2 = p->Data2 + q->Data2;
			//多项式相乘，系数相乘，指数相加
			d->Next = s;
			s->Next = NULL;
			d = s;
			q = q->Next;
		}
		p = p->Next;
	}
	return c;
}
List new_List_sort(List L) {//进行查重，将相同的指数数据相加
	List p = L->Next;
	while (p != NULL) {
		List q = p->Next;
		while (q != NULL) {
			if (p->Data2 == q->Data2) {
				p->Data1 += q->Data1;
				q->Data1 = 0;
			}
			q = q->Next;
		}
		p = p->Next;
	}
	return L;
}
int main() {
	List a = makeEmpty();
	List b = makeEmpty();
	int na, nb;
	printf("请分别输入多项式a与多项式b的非0系数的个数：\n");
	scanf("%d %d", &na, &nb);
	printf("请输入多项式a的各项系数与指数：\n");
	ElementType x, y;
	if (na != 0) {//输入应确保每个多项式的指数没有相同的
		//因为在多项式中指数相同的元素应该已经相加好了
		while (na--) {
			scanf("%d %d", &x, &y);
			a = Insert(a, x, y, Length(a) + 1);//将新加入的元素插到表尾
		}
	}
	if (nb != 0) {
		printf("请输入多项式b的各项系数与指数：\n");
		while (nb--) {
			scanf("%d %d", &x, &y);
			b = Insert(b, x, y, Length(b) + 1);//将新加入的元素插到表尾
		}
	}
	List c = Multiplication(a, b);//多项式相乘
	List_sort(c);//将相乘后的线性表去除0系数的元素并进行按指数大小的从大到小的排序
	new_List_sort(c);//将相乘后的链表进行查找，防止出现有指数相同的两个结点
	printf("两个多项式相乘后得到的结果为：\n");
	print(c);//直接输出相乘完之后的多项式
	return 0;
}
